package z_exam;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/7 19:28
 */

public class 快排 {

    //快速排序的基本思想是，从序列中任选一个元素，但通常会直接选择序列的第一个元素作为一个标准，所有比该元素值小的元素全部移动到他的左边，比他大的都移动到他的右边。我们称这叫做一趟快速排序，位于该元素两边的子表继续进行快速排序算法直到整个序列都有序。该排序算法是目前为止，内部排序中效率最高的排序算法。
    static int partition(int[] array, int i, int j){
        //数组第一个元素作为基准
        int temp = array[i];
        while(i < j){
            //从右向左扫描找比temp小的
            while(i < j && array[j] >= temp){
                j--;
            }
            array[i] = array[j];
            //从左向右扫描找比temp大的
            while(i < j && array[i] <= temp){
                i++;
            }
            array[j] = array[i];
        }
        array[i] = temp;
        return i;
    }

    /**
     * 对array[i,j]中元素递增排序
     * @param array
     * @param i
     * @param j
     */
    static void quickSort(int[] array, int i, int j){
        if(i < j){
            //划分中间位置  arr[0, k-1] 都小于arr[k]，不过其中没有顺序
            int k = partition(array, i, j);
            quickSort(array, i, k - 1);
            quickSort(array, k + 1, j);
        }
    }

    public static void main(String[] args) {
        int[] array = {134,183,120,146,114,126,167,124,119};
        quickSort(array, 0, array.length - 1);
        System.out.println();
    }
}
